package primary.code04_List;

/**
 * Q：给定可能有环的两个链表，返回链表的第一个相交点，不相交则返回 null
 *
 * A：
 * 相交的三种情况（其他情况均是相交点）：
 * 1. 无环与无环相交
 * 2. 有环与有环相交与环外
 * 3. 有环与有环相交于环中
 *
 * 思路：
 * 1. 判断链表是否有环
 * 2. 均无环策略
 * 3. 均有环且入环节点相同策略
 * 4. 均有环且入环节点不相同策略
 */
public class Code06_IntersectionNodeList {

    /**
     * 获取入环节点
     *
     * @param head
     * @return
     */
    public static Node getEntryNode(Node head) {
        Node slow = head;
        Node fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {//有环
                slow = head;
                while (slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;//相交点
            }
        }
        return null;
    }

    /**
     * 获取两个无环链表的相交节点
     *
     * @param head1
     * @param head2
     * @param end   指定结束节点
     * @return
     */
    public static Node getIntersectionNodeNoCircleList(Node head1, Node head2, Node end) {
        int len1 = 0;
        int len2 = 0;
        Node cur1 = head1;
        Node cur2 = head2;
        while (cur1.next != null && cur1 != end) {//注意，两个条件要同时满足
            len1++;
            cur1 = cur1.next;
        }
        while (cur2.next != null && cur2 != end) {
            len2++;
            cur2 = cur2.next;
        }
        if (cur1 != cur2) return null;//无相交点
        cur1 = head1;
        cur2 = head2;
        if (len1 > len2) {
            for (int i = 0; i < Math.abs(len1 - len2); i++) {
                cur1 = cur1.next;
            }
        } else {
            for (int i = 0; i < Math.abs(len1 - len2); i++) {
                cur2 = cur2.next;
            }
        }
        while (cur1 != cur2) {
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return cur1;
    }

    /**
     * 返回两个链表的相交节点
     *
     * @param head1
     * @param head2
     * @return
     */
    public static Node getIntersectNode(Node head1, Node head2) {
        Node entry1 = getEntryNode(head1);
        Node entry2 = getEntryNode(head2);
        if (entry1 == null && entry2 != null) return null;
        else if (entry1 != null && entry2 == null) return null;
        else if (entry1 == null && entry2 == null) {//两个无环链表
            return getIntersectionNodeNoCircleList(head1, head2, null);
        } else {//两个有环节点
            if (entry1 == entry2) {//入环节点前相交
                return getIntersectionNodeNoCircleList(head1, head2, entry1);
            } else {
                Node temp = entry1;
                while (temp != entry2) {
                    temp = temp.next;
                    if (temp == entry1) return null;
                }
                return entry1;
            }
        }
    }

    public static Node getIntersectNode0(Node head1, Node head2) {
        Node entryNode1 = getEntryNode0(head1);
        Node entryNode2 = getEntryNode0(head2);
        if ((entryNode1 == null && entryNode2 != null) || (entryNode1 != null && entryNode2 == null)) return null;
        if (entryNode1 == null) {
            return getIntersectNodeNoCircleList0(head1, head2, null);
        }

        if (entryNode1 == entryNode2) {
            return getIntersectNodeNoCircleList0(head1, head2, entryNode1.next);
        } else {
            Node temp = entryNode1.next;
            while (temp != entryNode1) {
                if (temp == entryNode2) {
                    return entryNode1;
                }
                temp = temp.next;
            }
            return null;
        }
    }

    public static Node getEntryNode0(Node head) {
        if (head == null || head.next == null || head.next.next == null) return null;
        Node s = head.next;
        Node f = head.next.next;
        while (s != f && f.next != null && f.next.next != null) {
            s = s.next;
            f = f.next.next;
        }
        if (s != f) {
            return null;
        }
        s = head;
        while (s != f) {
            s = s.next;
            f = f.next;
        }
        return s;
    }

    private static Node getIntersectNodeNoCircleList0(Node head1, Node head2, Node end) {
        Node p1 = head1;
        Node p2 = head2;
        int count1 = 0;
        int count2 = 0;
        while (p1.next != end) {
            count1++;
            p1 = p1.next;
        }
        while (p2.next != end) {
            count2++;
            p2 = p2.next;
        }
        if (p1 != p2) {
            return null;
        } else {
            p1 = head1;
            p2 = head2;
            int abs = Math.abs(count1 - count2);
            if (count1 > count2) {
                for (int i = 0; i < abs; i++) {
                    p1 = p1.next;
                }
            } else {
                for (int i = 0; i < abs; i++) {
                    p2 = p2.next;
                }
            }
            while (p1 != p2) {
                p1 = p1.next;
                p2 = p2.next;
            }
            return p1;
        }
    }

    /**
     * null
     * 6
     * null
     * 2
     * 4
     */
    public static void main(String[] args) {
        // 1->2->3->4->5->6->7->null
        Node head1 = new Node(1);
        head1.next = new Node(2);
        head1.next.next = new Node(3);
        head1.next.next.next = new Node(4);
        head1.next.next.next.next = new Node(5);
        head1.next.next.next.next.next = new Node(6);
        head1.next.next.next.next.next.next = new Node(7);

        Node head3 = new Node(1);
        head3.next = new Node(2);
        head3.next.next = new Node(3);
        head3.next.next.next = new Node(4);
        head3.next.next.next.next = new Node(5);
        head3.next.next.next.next.next = new Node(6);
        head3.next.next.next.next.next.next = new Node(7);
        System.out.println(getIntersectNode0(head1, head3) == null ? null : getIntersectNode0(head1, head3).data);

        // 0->9->8->6->7->null
        Node head2 = new Node(0);
        head2.next = new Node(9);
        head2.next.next = new Node(8);
        head2.next.next.next = head1.next.next.next.next.next; // 8->6
        System.out.println(getIntersectNode0(head1, head2) == null ? null : getIntersectNode0(head1, head2).data);//6 两无环链表，相交

        // 1->2->3->4->5->6->7->4...
        head1 = new Node(1);
        head1.next = new Node(2);
        head1.next.next = new Node(3);
        head1.next.next.next = new Node(4);
        head1.next.next.next.next = new Node(5);
        head1.next.next.next.next.next = new Node(6);
        head1.next.next.next.next.next.next = new Node(7);
        head1.next.next.next.next.next.next = head1.next.next.next; // 7->4

        head3 = new Node(1);
        head3.next = new Node(2);
        head3.next.next = new Node(3);
        head3.next.next.next = new Node(4);
        head3.next.next.next.next = new Node(5);
        head3.next.next.next.next.next = new Node(6);
        head3.next.next.next.next.next.next = new Node(7);
        head3.next.next.next.next.next.next = head3.next.next.next; // 7->4
        System.out.println(getIntersectNode0(head1, head3) == null ? null : getIntersectNode0(head1, head3).data);//两有环链表，不相交


        // 0->9->8->2...
        head2 = new Node(0);
        head2.next = new Node(9);
        head2.next.next = new Node(8);
        head2.next.next.next = head1.next; // 8->2
        System.out.println(getIntersectNode0(head1, head2) == null ? null : getIntersectNode0(head1, head2).data);//2 两有环链表，入环节点前相交

        // 0->9->8->6->4->5->6..
        head2 = new Node(0);
        head2.next = new Node(9);
        head2.next.next = new Node(8);
        head2.next.next.next = head1.next.next.next.next.next; // 8->6
        System.out.println(getIntersectNode0(head1, head2) == null ? null : getIntersectNode0(head1, head2).data);//4 or 6   两有环链表，入环节点后相交
    }
}
